import Interface.IArraySort;

public class QuickSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) {
        method(sourceArray,0,sourceArray.length-1);
        return sourceArray;
    }

    static void method(int[] nums, int l, int r) {
        if(l >= r) return;
        int i = l, j = r;
        //pivot基准数
        int pivot = nums[l];
        while(i < j) {
            while( nums[j]>=pivot && i < j) j--;
            while(nums[i]<=pivot&& i < j) i++;
            //i指针比基准数大，j指针比基准数小时，交换
            //交换，i,j指针对应的数字。
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        //i，j指针相遇,基准数与i指针互换.
        nums[l]=nums[i];
        nums[i] = pivot;
        method(nums, l, i - 1);
        method(nums, i + 1, r);
    }
}
class test{
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
       int[] arr= new int[]{2,8,1,7,5};
        quickSort.sort(arr);
        for(int i:arr){
            System.out.println(i);
        }
    }
}
